package cn.lishiyuan.leetcode;

/**
 * 逆序对统计
 *
 */
public class InversionPair {

    /**
     * 循环统计
     * @param nums
     * @return
     */
    public static int resolveCycle(int[] nums){
        int sum = 0;
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j < nums.length; j++){
                if (nums[i] > nums[j]){
                    sum ++;
                }
            }
        }
        return sum;
    }


    /**
     * 分治法解决
     * @param nums
     * @return
     */
    public static int resolveDAC(int[] nums){
        return dac(nums,0,nums.length-1);
    }


    private static int dac(int[] nums,int start,int end){
        if (end <= start){
            return 0;
        }
        int mid = start + (end - start)/2;
        int pL= dac(nums,start,mid);
        int pR= dac(nums,mid+1,end);
        int pM= merge(nums,start,mid,end);
        return pL+pR+pM;
    }

    private static int merge(int[] nums, int start, int mid, int end) {
        int count = 0;

        int i = start;
        int j = mid + 1;
        int[] l = new int[(end - start) + 1];
        for(int k = 0; k < l.length; k++){
            // 如果左边已经完全到达末尾则将右边放进去就行
            if(i > mid){
                l[k] = nums[j];
                j++;
                continue;
            }
            // 如果右边已经完全到达末尾则将左边放进去就行
            if(j > end){
                l[k] = nums[i];
                i++;
                continue;
            }
            // 将小的那个放入
            if (nums[i] <= nums[j]) {
                l[k] = nums[i];
                i++;
            }else {
                l[k] = nums[j];
                // 逆序了统计逆序个数
                // 由于左右两边都是有序的，如果i位置大于当前元素，那么i之后的所有元素都大于这个元素，也就是逆序的
                count += (mid - i + 1);
                j++;
            }
        }

        // 将有序的元素放入原合集
        System.arraycopy(l, 0, nums, start, l.length);

        return count;
    }


}
